package leetcode.滑动窗口;

/**
 * 长度最小的子数组
 *
 * 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。
 * 如果不存在符合条件的连续子数组，返回 0。
 */
public class Test209长度最小的子数组 {


    /**
     * 解法：滑动窗口
     * 维护一个窗口在数组上移动，不断扩大窗口直到元素和大于 s
     * 然后缩小窗口左边界，缩小后若窗口内元素和任然大于 s 就接着缩小，不然就扩大右边界
     *
     * 还需要一个记录最小窗口的值，并不断更新它
     */

    public static int minSubArrayLen(int s, int[] nums) {
        int l = 0;
        int r = -1; // 因为滑动窗口要不断增大的话， right 边界必须是从 0 慢慢增加的
        int minLength = nums.length + 1;
        int sum = 0;

        // 窗口可以一直滑到最后一个元素上，也就是单个元素就可以满足条件
        while (l < nums.length) {
            if (r + 1 < nums.length && sum <= s) {
                sum += nums[++r];
            } else {
                sum -= nums[l++];
            }
            // 获取满足条件的 minLength
            if (sum >= s) {
                minLength = Math.min(minLength, r - l + 1);
            }
        }

        if (minLength == nums.length + 1) {
            return 0;
        }
        return minLength;
    }

    public static void main(String[] args) {
        int s = 7;
        int[] nums = new int[]{2,3,1,2,4,3};
        System.out.println(minSubArrayLen(s, nums));
    }
}
